package com.topInterview;

public class Leecode152 {
    public int process(int[] value) {
        int N = value.length;
        //最小累乘积
        int[] dpMin = new int[N];
        //最大累成积
        int[] dpMax = new int[N];
        dpMax[0] = value[0];
        dpMin[0] = value[0];
        int res = dpMax[0];
        for (int i = 1; i < value.length; i++) {
            dpMax[i] = Math.max(value[i], Math.max(value[i] * dpMax[i - 1], value[i] * dpMin[i - 1]));
            dpMin[i] = Math.min(value[i], Math.min(dpMin[i - 1] * value[i], dpMax[i - 1] * value[i]));
            res = Math.max(res, dpMax[i]);
        }
        return res;
    }

    //求解最大累乘积
    // 当前位置最大，当前位置* i-1位置最小，当前位置*i-1位置最大
    public int process2(int[] value) {
        int min = value[0];
        int max = value[0];
        int res = value[0];
        for (int i = 1; i < value.length; i++) {
            int curMax = Math.max(value[i], Math.max(value[i] * min, value[i] * max));
            int curMin = Math.min(value[i], Math.min(value[i] * min, value[i] * min));
            min = curMin;
            max = curMax;
            res = Math.max(max, res);
        }
        return res;
    }
}
